package leetcode.array.other;

/**
 * 11. 盛最多水的容器
 *
 * 求数组对应的最大面积
 *
 */
public class WaterMaxArea {
    public static void main(String[] args) {
        WaterMaxArea waterMaxArea = new WaterMaxArea();

        int[] nums = {1, 3, 2, 5, 25, 24, 5};
        int area = waterMaxArea.maxArea(nums);
        System.out.println(area);
    }

    /**
     *
     * 错误的原因
     *      每次选择移动哪个指针的时候, 选择了下一步面积较大的那个指针
     *
     * @param height 数组
     * @return
     */
    public int maxArea0(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n - 1;
        // 最大面积
        int maxArea = getArea(height, left, right);
        while (left < right) {
            maxArea = Math.max(maxArea, getArea(height, left, right));
            int leftArea = getArea(height, left + 1, right);
            int rightArea = getArea(height, left, right - 1);
            if (leftArea > rightArea) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }


    /**
     *
     * 正确做法
     *      每次选择移动哪个指针的时候, 选择移动高度较小的那个指针
     *
     * @param height 数组
     * @return
     */
    public int maxArea(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n - 1;
        // 最大面积
        int maxArea = getArea(height, left, right);
        while (left < right) {
            maxArea = Math.max(maxArea, getArea(height, left, right));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }


    /**
     * 求指定下标范围的面积
     */
    public int getArea(int[] height, int left, int right) {
        int len = right - left;
        int width = Math.min(height[left], height[right]);
        return len * width;
    }
}
